The present invention relates to computer systems and, more particularly, to clock synchronization in multiprocessor systems. A major objective of the invention is to provide an approach to clock synchronization scaleable to multi-processor systems with large numbers of processors.
Some computer applications, e.g., some database applications, time stamp certain operations. In principle, time stamping operations allows a sequence of such operations to be reconstructed, e.g., in the event of a software fault or system crash. However, the time stamps must be sufficiently accurate and precise to allow the sequence to be reconstructed properly.
High-precision time stamps have been provided using local clocks, which are typically free-running counters; the counters are typically driven by fixed-frequency system clock signals so that the counters count at a fixed rate. By locating it “near” a processor, a clock can be quickly accessed by software running on the processor so that access latency does not significantly impair accuracy. If “standard” time (i.e., “wall-clock time”) is required, a processor clock can be synchronized with a more remote standard-time clock (also know as a “wall clock”) upon initialization and perhaps periodically after that.
This approach works well for single-processor systems, especially where the clock is located within the processor itself. However, in a multi-processor system, some or all of the processors must access a common clock via external data paths, e.g., system buses or interconnect networks. The external data paths not only impose longer latencies, but also impose significant variability in latencies—e.g., as bus or network contentions are resolved.
In a symmetric multiprocessing (SMP) system, an application can have multiple threads running on respective processors. If the different threads are subject to long and variable latencies, the time stamps may not be validly comparable across processors. As a result, operations can be mis-ordered upon reconstruction.
To reduce time-stamp latencies and their variability, each processor can have a local clock. To ensure synchronization of the clocks, they can be driven by a common clock signal. This can provide precise time stamps for simple SMP systems. However, failure of the clock-signal source causes failure of all the counters, which undermines fault tolerance otherwise provided by an SMP system. Also, as the multi-processor system scales, it can be difficult to transmit a single extremely high-frequency clock signal to a large number of components distributed across multi-processor integrated circuits and/or circuit boards.
Another approach is to use multiple counters and multiple clocks. Again each processor can have its own counter, while each counter can have its own clock signal. Alternatively, each clock signal can drive multiple counters-e.g., on the same board. In either case, clocks driven by different clock signals can “drift” relative to each other.
To address this drift, a software routine can quickly compare clock values for different processors and make any necessary correction values. The accuracy of the resulting corrections can be limited as the loads and stores required by the synchronization software are subject to the same unpredictable latencies suffered by all such transactions. If the software is run “on demand” when the main application requires a time stamp, the time stamps will be subject to inaccuracies due to the long and unpredictable latencies involved. Also, application programs designed to access a clock must be changed to call a more time-consuming software routine to obtain the time stamps. If the clock-calibration software is run in the background, it will consume computational power, incurring a significant performance penalty for the main applications. What is needed is a multiprocessor system that provides for accurate time stamps across processors while minimizing any impact on the main-application performance.